package problems;

import java.util.Set;
import java.util.logging.Logger;

import lib.Fraction;
import lib.MathLib;

import org.junit.Ignore;

@Ignore("too slow; use Euler069Fast instead")
public class Euler069 extends AbstractEuler {

	private Logger logger = Logger.getLogger(getClass().getName());
	
	@Override
	public Number calculate() {
		Fraction maxNDivPhiN = new Fraction(0,1);
		int maxNDivPhiNFor = 0;
		for (int i = 1; i <= 1000000; i++) {
			Fraction nDivPhiN = new Fraction(i,totient(i));
			if (nDivPhiN.compareTo(maxNDivPhiN) > 0) {
				maxNDivPhiN = nDivPhiN;
				maxNDivPhiNFor = i;
				logger.info("new max for n = " + i + ": " + nDivPhiN + " (" + nDivPhiN.normalized() + ")");
			}
		}
		return maxNDivPhiNFor;
	}

	@Override
	protected Number getCorrectAnswer() {
		return 510510;
	}
	
	public void testPhi36() {
		assertEquals(12, totient(36));
	}
	
	public static int totient(int n) {
		if (n == 1) return 1;
		Set<Integer> factors = MathLib.distinctFactors(n);
		Fraction result = new Fraction(n, 1);
		for (Integer factor : factors) {
			result = result.times(new Fraction(factor - 1, factor));
		}
		return result.intValue();
	}

}
